// https://www.lintcode.com/problem/max-tree/description

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param A: Given an integer array with no duplicates.
     * @return: The root of max tree.
     */
     
    // TLE
    // TreeNode * maxTree(vector<int> &A) {
    //     if (A.empty()) {
    //         return NULL;
    //     }
    //     priority_queue<int> q;
    //     for (int i = 0; i < A.size(); ++i) {
    //         q.push(A[i]);
    //     }
    //     int tmp = q.top();
    //     TreeNode * root = new TreeNode(tmp);
    //     q.pop();
    //     vector<int>::iterator idx = find(A.begin(), A.end(), tmp);
    //     vector<int> l(A.begin(), idx);
    //     vector<int> r(idx + 1, A.end());
    //     root->left = maxTree(l);
    //     root->right = maxTree(r);
    //     return root;
    // }
    
    
    // 法二：单调栈,每个值的父亲是min{左边第一个比它大的值，右边第一个比它大的值}
    TreeNode * maxTree(vector<int> &A) {
        if (A.empty()) {
            return NULL;
        }
        vector<TreeNode*> s;
        for (int i = 0; i <= A.size(); ++i) {
            int tmp;
            TreeNode * rightNode;
            if (i == A.size()) {
                tmp = INT_MAX;
                rightNode = new TreeNode(tmp);
            } else {
                tmp = A[i];
                rightNode = new TreeNode(tmp);
            }
            while (!s.empty() && s.back()->val <= tmp) {
                TreeNode * node = s.back();
                s.pop_back();
                if (!s.empty()) 
                {
                    TreeNode * leftNode = s.back();
                    if (tmp < leftNode->val) {
                        rightNode->left = node;
                    } else {
                        leftNode->right = node;
                    }
                } else {
                    rightNode->left = node;
                }
            }
            s.push_back(rightNode);
        }
        // return s[0];
        return s.back()->left; //注意，最后栈里面只有INT_MAX那个节点，它的leftnode是root
    }
    
    
    // 写法二
    // vector<TreeNode *> stk;
    // TreeNode* maxTree(vector<int> A) {
    //     // write your code here
    //     int len = A.size();
    //     for (int i = 0; i < len; ++i) {
    //         TreeNode *tmp = new TreeNode(A[i]);   //新建节点
    //         while (stk.size() > 0 && A[i] > stk[stk.size()-1]->val) {   //如果stk中的最后一个节点比新节点小
    //             tmp->left = stk[stk.size()-1];      //当前新节点的左子树为stk的最后一个节点
    //             stk.pop_back();
    //         }
    //         if (stk.size() > 0)    					//如果stk不为空
    //             stk[stk.size()-1]->right = tmp;		//将新节点设为stk最后一个节点的右子树
    //         stk.push_back(tmp);
    //     }
    //     return stk[0];
    // }
};